package _dp

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/house-robber-iii/description/
 * https://blog.csdn.net/2303_79786049/article/details/141503133
 * https://leetcode.cn/problems/house-robber-iii/solutions/67467/tong-yong-si-lu-tuan-mie-da-jia-jie-she-wen-ti-b-2
 *
 * 题型 ： 动态规划 + 二叉树后序遍历
 * 在二叉树上使用DP，汇总sum 时，对每个节点考虑两种情况：1) 打劫当前节点，2) 不打劫当前节点，打劫左右节点
 *
 * ```
 * 337. 打家劫舍 III
 *
 * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 *
 * 示例 1:
 * https://assets.leetcode.com/uploads/2021/03/10/rob1-tree.jpg
 * 输入: root = [3,2,3,null,3,null,1]
 * 输出: 7
 * 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
 *
 * 示例 2:
 * https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg
 * 输入: root = [3,4,5,1,3,null,1]
 * 输出: 9
 * 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
 *
 * 提示：
 * 树的节点数在 [1, 104] 范围内
 * 0 <= Node.val <= 104
 * ```
 */
class leetcode_337 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n3_2 = TreeNode(3)
        val n3_3 = TreeNode(3)
        val root = n3
        n3.left = n2
        n3.right = n3_2
        n2.right = n3_3
        n3_2.right = n1
        val actual = rob(root)
        val expected = 7
        Assert.assertEquals(actual, expected)
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n1_2 = TreeNode(1)
        val n3 = TreeNode(3)
        val n3_2 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val root = n3
        n3.left = n4
        n3.right = n5
        n4.left = n1
        n4.right = n3_2
        n5.right = n1
        val actual = rob(root)
        val expected = 9
        Assert.assertEquals(actual, expected)
    }


    @Test
    fun test_60() {
        /**
         *         4
         *        /
         *       1
         *      /
         *    2
         *   /
         *  3
         */
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root = n4
        n4.left = n1
        n1.left = n2
        n2.left = n3
        val actual = rob(root)
        val expected = 7
        Assert.assertEquals(actual, expected)
    }


    private fun rob(root: TreeNode?): Int {
        /**
        思路：动态规划 ：在二叉树上使用DP，遍历顺序为后序遍历。
        汇总sum 时，对每个节点考虑两种情况：1) 打劫当前节点，2) 不打劫当前节点，打劫左右节点
         */

        val sumPair: Pair<Int, Int> = f(root)
        return Math.max(sumPair.first, sumPair.second)
    }

    // 1 确认函数参数以及返回值
    private fun f(root: TreeNode?): Pair<Int, Int> { // Pair<打劫当前节点，不打劫当前节点>

        // 2 确认终止条件
        if (null == root) {
            return Pair<Int, Int>(0, 0)
        }

        // 3 确认单层递归的逻辑：左右中
        // 左
        val leftSum: Pair<Int, Int> = f(root.left)

        // 右
        val rightSum: Pair<Int, Int> = f(root.right)

        // 中
        // 1) 打劫当前节点
        // 当前节点值 + 左子节点不偷的最大金额 + 右子节点不偷的最大金额
        val robCurrentSum = root.`val` + leftSum.second + rightSum.second

        // TODO:2) 不打劫当前节点，打劫左右节点
        // 左子树：取 "偷左子树" 和 "不偷左子树" 中的较大值
        // 右子树：取 "偷右子树" 和 "不偷右子树" 中的较大值
        // 不偷当前节点，则可以偷也可以不偷左右子节点，分别取左右子树在两种状态下的较大值相加 -- 注意：在这里左右子树是分开考虑的
        val notRobCurrenSum = Math.max(leftSum.first, leftSum.second) + Math.max(rightSum.first, rightSum.second)

        return Pair<Int, Int>(robCurrentSum, notRobCurrenSum)
    }

    fun rob2(root: TreeNode?): Int {
        val result: Result = collect(root)
        return Math.max(result.rob, result.notRob)
    }

    fun collect(root: TreeNode?): Result{
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if(null == root){
            return Result(0,0)
        }
        // 3 确定单层递归的处理逻辑：后序遍历
        // 左
        val left = collect(root.left)
        // 右
        val right = collect(root.right)

        // 中
        // 1) 打劫当前节点
        val v1 = root.`val` + left.notRob + right.notRob
        // TODO:2) 不打劫当前节点，打劫左右节点
        // 不偷当前节点，则可以偷也可以不偷左右子节点，分别取左右子树在两种状态下的较大值相加 -- 注意：在这里左右子树是分开考虑的
        val v2 = Math.max(left.rob , left.notRob) + Math.max(right.rob, right.notRob)
        return Result(v1, v2)
    }
    data class Result(var rob: Int, var notRob: Int)
}